package Algorithm.list;

/**
 * @Desc: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 合并两个有序链表
 *
 * 示例：
 *
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * 就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表 l1l1 和 l2l2 的表头开始相加。
 * 由于每位数字都应当处于 0 \ldots 90…9 的范围内，我们计算两个数字的和时可能会出现 “溢出”。
 * 例如，5 + 7 = 125+7=12。在这种情况下，我们会将当前位的数值设置为 22，并将进位 carry = 1carry=1
 * 带入下一次迭代。进位 carrycarry 必定是 00 或 11，这是因为两个数字相加（考虑到进位）
 * 可能出现的最大和为 9 + 9 + 1 = 199+9+1=19。
 *

 *
 * @author: cww
 * @DateTime: 2020/4/10 20:09
 */

public class MergeTwoLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                head.next = l1;
                l1 = l1.next;
            }else{
                head.next = l2;
                l2 = l2.next;
            }
            // 注意要将头右移
            head = head.next;
        }
        head.next = l1 == null? l2:l1;
        return dummy.next;

    }

    public ListNode mergeTwoLists1(ListNode l1, ListNode l2){
        ListNode dumy = new ListNode(-1);
        ListNode head = dumy;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
                head.next = l2;
                l2 = l2.next;
            }else {
                head.next = l1;
                l1 = l1.next;
            }
            head = head.next;
        }
        head.next = l1 ==null?l2:l1;
        return dumy.next;
    }
}

